#ifndef WTK_CORE_WTK_MAX_HEAP_H_
#define WTK_CORE_WTK_MAX_HEAP_H_

#ifdef __cplusplus
extern "C" {
#endif
#include "wtk/core/wtk_alloc.h"
#include <stdlib.h>

typedef int (*wtk_max_heap_cmp_t)(void * a, void * b);


struct wtk_max_heap
{
    void ** array;
    wtk_max_heap_cmp_t cmp;
    float rate;
    int length;
    int pos;
};
typedef struct wtk_max_heap wtk_max_heap_t;

static inline wtk_max_heap_t * wtk_max_heap_new(int len, float rate, wtk_max_heap_cmp_t cmp)
{
    wtk_max_heap_t * heap = (wtk_max_heap_t *)malloc(sizeof(wtk_max_heap_t));
    heap->array = (void**)malloc(sizeof(void *) * len);
    heap->rate = rate;
    heap->length = len;
    heap->cmp = cmp;
    heap->pos = 0;
    return heap;
}

static inline void wtk_max_heap_reset(wtk_max_heap_t * heap)
{
    heap->pos = 0;
}

static inline void wtk_max_heap_delete(wtk_max_heap_t * heap)
{
    free(heap->array);
    free(heap);
}

static inline void wtk_max_heap_insert(wtk_max_heap_t * heap, void * data)
{
    void **array;
    void * tmp_p;
    int left;
    size_t alloc;
    int t1;
    int i;
    int parent;

    left = heap->length - heap->pos;
    if(left <= 0)
    {
        alloc = heap->length + 1;
        t1 = heap->length * heap->rate;
        alloc = alloc>t1?alloc:t1;
        heap->array = (void **)realloc(heap->array, alloc * sizeof(void *));
        heap->length = alloc;
    }
    array = heap->array;
    i = (heap->pos)++;
    array[i]= data;
    parent = (i-1)/2;
    
    while(i != 0 && heap->cmp(array[parent] , data) < 0)
    {
        tmp_p = array[parent];
        array[parent] = data;
        array[i] = tmp_p;
        i = parent;
        data = array[i];
        parent = (i-1)/2;
    }
}

static inline void wtk_max_heap_heapify(wtk_max_heap_t * heap, int i)
{
    void ** array = heap->array;
    int heap_size = heap->pos;
    int l = (i<<1) + 1;
    int r = (i<<1) + 2;
    int chosen = i;
    void * tmp_p;
    
    if(l < heap_size && heap->cmp(array[l], array[chosen]) > 0)
    {
        chosen = l;
    }

    if(r < heap_size && heap->cmp(array[r], array[chosen]) > 0)
    {
        chosen = r;
    }

    if(chosen != i)
    {
        tmp_p = array[chosen];
        array[chosen] = array[i];
        array[i] = tmp_p;
        wtk_max_heap_heapify(heap, chosen);
    }
}

static inline void * wtk_max_heap_pop(wtk_max_heap_t * heap)
{
    void  * root;
    void ** array;
    
    if(heap->pos <=0)
        return NULL;
    if(heap->pos == 1)
    {
        --(heap->pos);
        return heap->array[0];
    }
    array = heap->array;
    root = array[0];
    array[0] = array[--(heap->pos)];

    wtk_max_heap_heapify(heap, 0);
    return root;
}

#ifdef __cplusplus
};
#endif

#endif
